# -*- coding: utf-8 -*-

class YangHuiTriangle():
    def __init__(self, *x):
        """用一个数组来保存杨辉三角"""
        self.head = [0,]
        self.head.extend(x)
        self.flr =[0,]
        self.init_flr()
    
    def init_flr(self):
        count = len(self.head)-1
        f = 1
        while True:
            first_idx = f*(f-1)//2+1
            if first_idx < count:
                self.flr.append(first_idx)
            else:
                break
            f += 1

    def select_flr(self, idx):
        """用二分查找最后一个小于等于idx的索引"""
        fmin, fmax = 1, len(self.flr)-1
        def erfen(fmin, fmax):
            if fmax-fmin == 1:
                if self.flr[fmax] <= idx:
                    return fmax
                else:
                    return fmin
            fmiddle = (fmin+fmax)//2
            if self.flr[fmiddle] == idx:
                
                if self.flr[fmiddle+1] == idx:
                    fmin, fmax = fmiddle+1, fmax
                    erfen(fmin, fmax)
                else:
                    return fmiddle
            elif self.flr[fmiddle] < idx:
                fmin, fmax = fmiddle, fmax
                return erfen(fmin, fmax)
            else:
                fmin, fmax = fmin, fmiddle
                return erfen(fmin, fmax)
        return erfen(fmin, fmax)
    
    def calc_min_distance_in_divide(self):
        """用分治的方法"""
        def min_dist(idx):
            flr = self.select_flr(idx)
            if flr == len(self.flr)-1:
                return 0, []
            
            idx_left, idx_right = idx+flr, idx+flr+1
            
            min_left, min_right = min_dist(idx_left), min_dist(idx_right)
            
            min_dist_left, scheme_left, min_dist_right, scheme_right = min_left[0], min_left[1], min_right[0], min_right[1]
            dist_left, dist_right = min_dist_left+self.head[idx_left], min_dist_right+self.head[idx_right]

            if dist_left <= dist_right:
                scheme_left.append(idx_left)
                return dist_left, scheme_left
            else:
                scheme_right.append(idx_right)
                return dist_right, scheme_right
        
        m = min_dist(1)
        dist = m[0]+self.head[1]
        scheme = m[1]
        scheme.append(1)
        scheme.reverse()
        return dist, scheme

    def calc_min_distance_in_dynamic(self):
        """用动态规划的方法"""


if __name__ == '__main__':
    triangle = YangHuiTriangle(5, 7,8, 2,3,4, 4,9,6,1, 2,7,9,4,5)
    print(triangle.head)
    print(triangle.flr)
    min_dist = triangle.calc_min_distance_in_divide()
    print(min_dist)
